package com.lfg.leetcode.leetcode100;

import com.lfg.leetcode.leetcode0.TreeNode;

import java.util.HashMap;
import java.util.Map;


public class No105buildTree {
    public static void main(String[] args) {
        TreeNode ret = buildTree(new int[]{1, 2, 3}, new int[]{3, 2, 1});
        System.out.println("[" + ret + "]");
    }

    private static Map<Integer,Integer> inorderMap = new HashMap<>();

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length != inorder.length) {
            return null;
        }
        for (int i=0;i<inorder.length;i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }


    public static TreeNode buildTree(int[] preorder, int pStartIndex, int pEndIndex, int[] inorder, int iStartIndex, int iEndIndex) {
        if (pStartIndex < 0 || pStartIndex > pEndIndex || pEndIndex >= preorder.length) {
            return null;
        }
        TreeNode ret = new TreeNode(preorder[pStartIndex]);
        if (pStartIndex == pEndIndex) {
            return ret;
        }
        int root = preorder[pStartIndex];
        int iOrderIndex = inorderMap.get(root);
        int pEndIndex1 = pStartIndex + iOrderIndex - iStartIndex;
        ret.left = buildTree(preorder, pStartIndex + 1, pEndIndex1, inorder, iStartIndex, iOrderIndex - 1);
        ret.right = buildTree(preorder, pEndIndex1 + 1, pEndIndex, inorder, iOrderIndex + 1, iEndIndex);
        return ret;
    }
}
